package array

import "sort"

// 官方动态规划的答案
// 结果超出时间限制？？？？？？？
func eraseOverlapIntervals1(intervals [][]int) int {
	length := len(intervals)
	if length == 0 {
		return 0
	}

	countSlice := make([]int, length)
	for i := 0; i < length; i++ {
		countSlice[i] = 1
	}

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	for i := 1; i < length; i++ {
		for j := 0; j < i; j++ {
			if intervals[j][1] <= intervals[i][0] {
				countSlice[i] = max(countSlice[j]+1, countSlice[i])
			}
		}
	}

	return length - max(countSlice...)

}

func max(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if a[i] > res {
			res = a[i]
		}
	}

	return res
}

func eraseOverlapIntervals2(intervals [][]int) int {
	length := len(intervals)
	if length == 0 {
		return 0
	}

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][1] < intervals[j][1]
	})

	ans, right := 1, intervals[0][1]

	for _, v := range intervals[1:] {
		if v[0] >= right {
			ans++
			right = v[1]
		}
	}

	return length - ans

}
